#ifndef HFM_TREE_H
#define HFM_TREE_H
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include "BSTree.hpp"
#include "sort.hpp"
using namespace std;
const char EMPTY_HFM_NODE_CODE_CH  = '\0';
class HFMCode{
public:
    HFMCode(char ch, int weight):ch(ch),weight(weight){}
    ~HFMCode(){}
    string toString(){
        const string format = R"(HFMCode{"ch": %s, "weight": %d})";
        char *buf = new char[(int)(format.length() * 1.5)];
        string str = "";
        if(ch != EMPTY_HFM_NODE_CODE_CH){
            str.push_back(ch);
        }else{
            str +="nullNode";
        }
        sprintf(buf,format.c_str(),str.c_str(),weight);
        return string(buf);
    }
    char ch;
    int weight;

};
class HFMTreeNode{
public:
    bool isNullNode;
    HFMCode *hfmCode;
    HFMTreeNode *left;
    HFMTreeNode *right;
    HFMTreeNode(HFMCode *hfmCode, HFMTreeNode *left = nullptr, HFMTreeNode *right = nullptr,
                bool isNullNode = false)
                :hfmCode(hfmCode),left(left),right(right),
                isNullNode(isNullNode) {}
    ~HFMTreeNode(){
        hfmCode = nullptr;
        left = nullptr;
        right = nullptr;
    }
};
class HFMTree{
public:
    static map<char,string> encodeHfmCodeMap;
    static map<string ,char> decodeHfmCodeMap;
    HFMTree(){}
    ~HFMTree(){
    }
    /**
     * BADCADFEED   A 27，B 8，C 15，D 15，E 30，F 5       A 01 B 1001 C 00 D 101 E 11 F 1000
     *      原编码二进制串：001000011010000011101100100011（共30个字符）
     *      新编码二进制串：1001010010101001000111100（共25个字符）答案
     *                   100101101000110110001111101
     *                      因为buildHFMTree的方法，所以C 00 D 101，答案是D 00 C 101
     *                          因为有3个D，一个C，所以多出了2个
     */
    static const char EMPTY_HFM_NODE  = EMPTY_HFM_NODE_CODE_CH;
    static string encodeByHFMCode(const string& content){
        //计算权值
        vector<HFMCode*> hfmCodes;
        makeHFMCodes(content,hfmCodes);
        //构建哈夫曼树
        HFMTreeNode* root = buildHFMTree(hfmCodes);
        traverse_pre_recursion(root);
        //得到编码表
        makeHFMCodeMap(root, encodeHfmCodeMap,"");
        for_each(encodeHfmCodeMap.begin(),encodeHfmCodeMap.end(),
                 [=](pair<char,string> p)->void{cout<<p.first<<" "<<p.second<<endl;});

        string encodeContent = encode(content, encodeHfmCodeMap);
        return encodeContent;
    }
    static string decodeByHFMCode(const string& content, map<char,string>& encodeHfmCodeMap){
        for(const auto& code : encodeHfmCodeMap){
            decodeHfmCodeMap[code.second] = code.first;
        }
        string decodeContent;
        string temp;
        for(char ch : content){
            temp.push_back(ch);
            if(decodeHfmCodeMap.count(temp) != 0){
                decodeContent += decodeHfmCodeMap[temp];
                temp.clear();
            }
        }
        return decodeContent;
    }
    static string bytesToBinaryStr(const string& bytes){
        string binaries;
        for(const char ch : bytes){
            binaries += byteToBinaryStr(ch);
        }
        return binaries;
    }
    static string byteToBinaryStr(const char ch){
        string binary;
        int a = ch;
        while(a != 0){
            binary.push_back((a % 2) + '0');
            a /= 2;
        }
        std::reverse(binary.begin(), binary.end());
        while(binary.size() != 8){
            binary = "0" + binary;
        }
        return binary;
    }
private:
    static string encode(const string& content,const map<char,string>& hfmCodeMap){
        string encodeContent;
        for(char ch : content){
            encodeContent += hfmCodeMap.at(ch);
        }
        return encodeContent;
    }
    static void traverse_pre_recursion(HFMTreeNode* node){
        if(node == nullptr){
            return;
        }
        cout<<node->hfmCode->toString()<<endl;
        traverse_pre_recursion(node->left);
        traverse_pre_recursion(node->right);
    }
    static void makeHFMCodeMap(HFMTreeNode* node, map<char,string>& hfmCodeMap,string code){
        if(node == nullptr){
            return;
        }
        if(node->isNullNode){
            makeHFMCodeMap(node->left,hfmCodeMap,code  + "0");
            makeHFMCodeMap(node->right,hfmCodeMap,code  + "1");
        }else{
            hfmCodeMap[node->hfmCode->ch] = code;
        }
    }

    /**
     * 每次的最小weight2个节点组成一颗树，root是data=null，weight=2个节点的weight和
     * 为了容易删除，用降序，同权值的会把新生产的nullNode放到同权值的第一个
     */
    static HFMTreeNode* buildHFMTree(vector<HFMCode*>& hfmCodes){
        auto hfmCodeSort = [](HFMCode* back, HFMCode* front)->
                bool{return back->weight - front->weight > 0;};
        //第1个参数是后面的，第2个参数是前面的
        //必须返回bool true 交换
        //    return bool; back - front > 0   降序
        //                 front - back > 0   升序
        sort(hfmCodes.begin(), hfmCodes.end(),hfmCodeSort);

        vector<HFMTreeNode*> hfmCodeNodes;
        for(auto code : hfmCodes){
            hfmCodeNodes.push_back(new HFMTreeNode(code));
        }

        while(hfmCodeNodes.size() != 1){
            HFMTreeNode* big = hfmCodeNodes[hfmCodeNodes.size()-1];
            HFMTreeNode* small = hfmCodeNodes[hfmCodeNodes.size()-2];
            hfmCodeNodes.pop_back();
            hfmCodeNodes.pop_back();
            if(big->hfmCode->weight < small->hfmCode->weight){
                HFMTreeNode* t = big;
                big = small;
                small = t;
            }
            HFMTreeNode* nullHFMNode = new HFMTreeNode(
                    new HFMCode(EMPTY_HFM_NODE,small->hfmCode->weight + big->hfmCode->weight),
                    small,big, true
                    );
            int idx = -1;
            for (int i = hfmCodeNodes.size() - 1; i >= 0; --i) {
                if(nullHFMNode->hfmCode->weight < hfmCodeNodes[i]->hfmCode->weight){
                    idx = i;
                    break;
                }
            }
            if(idx == -1){
                //这样的好处是，当newHfmCodeNode->data->weight是最大的时候，可以直接插到head
                //而且如果最好剩2个时，也能合并为一个再插入hfmCodeNodes，此时hfmCodeNodes的size == 1 成立
                hfmCodeNodes.insert(hfmCodeNodes.begin(),nullHFMNode);
            }else{
                hfmCodeNodes.insert(hfmCodeNodes.begin() + idx + 1,nullHFMNode);
            }
        }
        return hfmCodeNodes[0];
    }
    /**
     * 每种字符出现次数
     * 或者自定义权值
     */
    static void makeHFMCodes(const string& content, vector<HFMCode*>& hfmCodes){
//        map<char,int> rightMap = {
//                {'A',27}, {'B',8}, {'C',15},{'D',15}, {'E',30}, {'F',5}
//        };
        map<char,int> rightMap;
        for (char i : content) {
//            rightMap[i] = 0;
            rightMap[i]++;
        }

        for (auto entry : rightMap) {
            hfmCodes.push_back(new HFMCode(entry.first,entry.second));
        }
    }
};
map<char,string> HFMTree::encodeHfmCodeMap;
map<string,char> HFMTree::decodeHfmCodeMap;
#endif //HFM_TREE_H